package com.markpim.algo;

public class MergeSort {

	public MergeSort(int[] input) {
		long timeSum = 0;
		for (int i = 0; i < Apl.ACCURACY; i++) {
			startTime = System.currentTimeMillis();
			assert Apl.isSorted(mergeSortRecursive(input)) : "Tried to mergesort but failed!";
			endTime = System.currentTimeMillis();
			timeSum += (endTime - startTime);
		}
		avgTime = timeSum / Apl.ACCURACY;
		done(input.length);
	}

	protected long startTime = 0;
	protected long endTime = 0;
	protected long operations = 0;
	protected long avgTime = 0;

	public void done(int count) {
		System.out.println("Mergesorted " + count + " integers");
		System.out.println("Sorted in " + avgTime
				+ " milliseconds");
		System.out.println(operations + " operations.");
		System.out.println(" -------------- ");
		System.out.println();
	}

	private int[] mergeSortRecursive(int[] numbers) {
		if (numbers.length > 1) {
			int elementsInA1 = numbers.length / 2;
			int elementsInA2 = elementsInA1;
			if ((numbers.length % 2) == 1)
				elementsInA2 += 1;
			int arr1[] = new int[elementsInA1];
			int arr2[] = new int[elementsInA2];
			for (int i = 0; i < elementsInA1; i++) {
				operations++;
				arr1[i] = numbers[i];
			}
			for (int i = elementsInA1; i < elementsInA1 + elementsInA2; i++) {
				operations++;
				arr2[i - elementsInA1] = numbers[i];
			}
			arr1 = mergeSortRecursive(arr1);
			arr2 = mergeSortRecursive(arr2);
			int i = 0, j = 0, k = 0;
			while (arr1.length != j && arr2.length != k) {
				operations++;
				if (arr1[j] < arr2[k]) {
					numbers[i] = arr1[j];
					i++;
					j++;
				} else {
					numbers[i] = arr2[k];
					i++;
					k++;
				}
			}
			while (arr1.length != j) {
				operations++;
				numbers[i] = arr1[j];
				i++;
				j++;
			}
			while (arr2.length != k) {
				operations++;
				numbers[i] = arr2[k];
				i++;
				k++;
			}
		}
		return numbers;
	}
}
